package com.nowc.week.w99;

import java.io.*;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class f {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        in.nextToken(); int t = (int) in.nval;
        while (t-- > 0) {
            in.nextToken();
            long n = (long) in.nval;
            in.nextToken();
            long m = (long) in.nval;
            long ans = 0;
            for (int bit = 30; bit >= 0; bit--) {
                long v = 1L << bit;
                long cost = m * v;
                if (n >= cost) {
                    ans |= (1L << bit);
                    n -=  cost;
                } else {
                    cost -= m;
                    if (n <= cost) {
                        continue;
                    }
                    long k = ((n - cost + v - 1) / v);
                    n -= k * v;
                }
            }
            out.println(ans);
        }
        out.flush();
        out.close();
        br.close();
    }
}